In modern society, digital data about individuals that could be considered to be highly personal, can be found relatively easily in the communication networks, especially the Internet. Although most people support the last decades' advances in digital networks, the sensitiveness of these data motivates an increasing concern about the public availability of personal data and the processing performed on them. On the other hand, signal processing researchers have traditionally focused on continuously improving the efficiency and robustness of the applied algorithms, while often leaving aside the crucial aspect of data privacy. Thus, advances in signal processing have not taken into account the trustworthiness of the parties that manage users' signals or the sensitiveness of the information contained within these signals. There are many application scenarios where the need for privacy is clearly present, mainly those in which biological signals (fingerprints, faces, iris, Deoxyribonucleic acid (DNA), Electrocardiogram (ECG) signals, Arterial Blood Pressure (ABP) signal, Magnetic Resonance Images (MRI), etc) are involved, as they hold extremely sensitive information about users or patients, and their privacy is traditionally addressed through written consents that represent the trust that users must put on the party or parties that process their signals.
Signal Processing in the Encrypted Domain (SPED) is an emergent research field that has arisen to effectively tackle the privacy problems involving signal processing. As an interdisciplinary area, it has faced from its birth the challenge of bringing together the views of the cryptographic and the signal processing communities in order to reach the target of efficiently applying privacy preserving techniques to common signal processing operations.
The theoretical grounds of Signal Processing in the Encrypted Domain come from the field of secure function evaluation, that was introduced by Yao in 1982 [1] (Secure two-party computation) through the now widely known Millionares' problem, and then generalized to Secure Multiparty Computation [2] (SMC). In the former setting, two millionaires wish to know who is the richest, without disclosing to the other their respective wealth. The solution proposed by Yao was based on the concept of garbled circuits. In spite of the generality of the presented solution, the inefficiency of its implementation for many applications has constituted the biggest obstacle for the development of this technology for many years, in such a way that the existence of efficient solutions for the secure execution of a generic function is still an open problem. Nonetheless, many efficient and secure techniques have been developed for specific applications in the past few years, building up a set of tools that foretell the potential of this technology.
Within this set of tools, the most efficient SPED primitives are those that exploit the properties of homomorphic encryption for performing some linear fixed operations, but most of the times Signal Processing needs to go further, resorting to adaptive filtering algorithms, due to their greater flexibility, higher responsiveness when tracking the changes in the environment, their convergence to the optimal fixed solution when working in a stationary environment, and the fact that they are the optimal solution in settings where the information about the signal characteristics is not complete, offering a much better performance than fixed filters. Hence, a considerable number of practical signal processing applications make use of adaptive filters. Unfortunately, the current homomorphic cryptosystems cannot directly deal with adaptive filters due to cipher blowup after a given number of iterations; on the other hand, full homomorphisms, like Gentry's [3], able of executing any circuit without the need of decryption, are still not practical, due to the huge size needed for the ciphertexts. In fact, the existence of practical fully homomorphic cryptosystems is still an open problem. Even though there are some linear transforms and basic operations that can be directly translated into homomorphic processing, the set is too limited, and when privacy is a concern, the solution cannot impose that these operations be replaced by simpler non-adaptive algorithms, as the negative impact on performance could virtually destroy the usefulness of the algorithm. This is especially true when the involved signals are not stationary, and the filter must track their changes over time.
Related work on private linear filtering has been presented as part of the Signal Processing in the EncryptEd Domain (SPEED) project [4], dealing with the privacy problem in a two-party setting where one party has an input to a linear filter and another party holds the filter coefficients. Such efficient privacy-preserving solutions are based solely on homomorphic processing, as it fits perfectly the linear filtering operation without imposing any overhead on communication. Within the area of linear filtering, we can point out the works by Bianchi et al. [5-7], dealing with encrypted Discrete Fourier Transform (DFT) and Discrete Cosine Transform (DST) and frequency-domain linear filtering. Additionally, these works discuss also the problem of disclosing data derived from the inputs without any dimensionality reduction, as the original data can be inferred from the disclosed outputs.
There have been also some contributions for more complex operations, involving the combination of garbled circuits and homomorphic processing, most notably those from Kolesnikov et al. [8], in which homomorphic processing is used for the linear operations, while garbled circuits deal with non-linear operations.
Regarding the privacy considerations in iterative algorithms, there are some contributions in the area of private collaborative filtering, like those by Canny [9] and Erkin [10]. In the former, Canny developed a privacy-preserving iterative conjugate gradient algorithm for the calculation of the Singular Value Decomposition (SVD) of a shared preference matrix P. The setting in [9] addresses a particular problem as follows: a) it involves multiple parties, and the gradient estimate in each iteration is calculated as the sum of the contributions from each of these parties; b) the result of every iteration is decrypted and disclosed before the next iteration; hence, it does not involve successive products of encrypted values, as each party uses only clear-text values for producing the results at every iteration; c) as a drawback, the disclosure of the approximation of the preference matrix and the global gradient calculated at each iteration are publicly known; hence, the security relies on those matrices having a very high dimension and the system having a very high number of users. However, when dealing with protecting the signals coming from one party during their adaptive filtering by another untrusted party; in this setting, Canny's solution loses its privacy properties, as the value disclosed after each iteration allows each party to calculate the secret input from the other party. Furthermore, it is necessary to keep all the intermediate values encrypted in order to effectively preserve the privacy of the involved users, and this involves repeated products of encrypted numbers that will have direct consequences on the viability of the used privacy-preserving techniques due to the cipher blowup problem.
Other private iterative algorithms involve K-means clustering of a database shared between two parties, like the one proposed by Jagannathan et al. [11]; again, in this setting, the results of each iteration (the current classification of the elements) are disclosed before the next, and the security relies on the dimensionality of the databases, unlike the case of private adaptive filtering.
Currently, there are no specific solutions within the emerging field of Signal Processing in the Encrypted Domain for securely executing iterative or adaptive filtering algorithms, nor any study performed on the impact that an iterative implementation has on the range of representable numbers when the results of each iteration cannot be disclosed. Consequently, there are currently no solutions dealing with privacy preserving adaptive filtering algorithms.